package BinaryTree;
import java.util.*;
public class BinaryTree {
    public TreeNode root;          //根节点
    public void creatTree() {      //临时创建二叉树
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        root=A;
    }
    public void preOrder(TreeNode root) {       //前序遍历
        if(root==null) {
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public void inOrder(TreeNode root) {          //中序遍历
        if(root==null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    public void postOrder(TreeNode root) {          //后序遍历
        if(root==null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> list=new ArrayList<>();
        if(root==null) {
            return list;
        }
        list.add(root.val);
        List<Character> leftTree=preorderTraversal(root.left);
        list.addAll(leftTree);
        List<Character> rightTree=preorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }
    //二叉树的基本操作
    //时间复杂度O(N)                      相当于遍历一遍，递归次数为n次
    //空间复杂度O(logN)[树的高度]~O(N)      最好情况:完全二叉树，遍历完所有左子树后，都会返回，然后空间释放，只剩下右子树，所以为logn最坏情况:单分支，全部是左子树
    public int size(TreeNode root) {      //获取结点个数（子问题:左树的结点+右树的结点+1（自己））子问题思想
        if(root==null) {
            return 0;
        }
        int leftSize=size(root.left);
        int rightSize=size(root.right);
        return leftSize+rightSize+1;
    }
    public int nodeSize;
    public void size1(TreeNode root) {      //遍历思想
        if(root==null) {
            return;
        }
        size1(root.left);
        size1(root.right);
        nodeSize++;
    }
    public int getLeafNodeCount(TreeNode root) {            //获取叶子结点个数(左树的叶子+右树的叶子)
        if(root==null) {
            return 0;
        }
        if(root.right==null&&root.left==null) {
            return 1;
        }
        int leftleafnode=getLeafNodeCount(root.left);
        int rightleafnode=getLeafNodeCount(root.right);
//        if(root.right==null&&root.left==null) {
//            return 1;
//        }
        return leftleafnode+rightleafnode;
    }
    public int leafCount;
    public void getLeafNodeCount1(TreeNode root) {
        if(root==null) {
            return;
        }
        if(root.right==null&&root.left==null) {
            leafCount++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }
    public int getLevelNodeCount(TreeNode root,int k) {                   //求第k层结点的个数（求左右子树的k-1层）
        if(root==null) {        //如果空节点那么这一层没有结点
            return 0;
        }
        if(k==1) {             //
            return 1;
        }
        int leftcount=getLevelNodeCount(root.left,k-1);
        int rightcount=getLevelNodeCount(root.right,k-1);
        return leftcount+rightcount;
    }
    public int getHeight(TreeNode root) {                               //左树的高度和右树的高度的最大值+1
       if(root==null) {
           return 0;
       }
       int leftheight=getHeight(root.left);
       int rightheight=getHeight(root.right);
       return (Math.max(leftheight, rightheight))+1;
    }
    public TreeNode find(TreeNode root,char val) {                      //判断值为value结点是否存在(遍历二叉树，找是否有val的值)
        if(root==null) {
            return null;
        }
        if(root.val==val) {
            return root;
        }
        TreeNode leftTree=find(root.left,val);
        if(leftTree!=null) {                                         //如果左边没有该节点就去右边找
            return leftTree;
        }
        TreeNode rightTree=find(root.right,val);
        if(rightTree!=null) {
            return rightTree;
        }
        return null;
    }
    public void levelOrder(TreeNode root) {                            //层序遍历
        if(root==null) {
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);     //使用队列
        while(!queue.isEmpty()) {
            TreeNode cur=queue.poll(); //出一个就能把左右两边的子树带出来
            System.out.print(cur.val+" ");
            if(cur.left!=null) {
                queue.offer(cur.left);
            }
            if(cur.right!=null) {
                queue.offer(cur.right);
            }
        }
    }
    public List<List<Character>> levelOrder1(TreeNode root) {
        if(root==null) {
            return new ArrayList<>();
        }
        List<List<Character>> list1=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            List<Character> list2=new ArrayList<>();
            int size=queue.size();
            while(size-->0) {
                TreeNode cur=queue.poll();
                list2.add(cur.val);
                if(cur.left!=null) {
                    queue.offer(cur.left);
                }
                if(cur.right!=null) {
                    queue.offer(cur.right);
                }
            }
            list1.add(list2);
        }
        return list1;
    }
    public List<List<Character>> levelOrderBottom(TreeNode root) {    //从后往前层序遍历
        List<List<Character>> list=new ArrayList<>();
        if(root==null) {
            return list;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            List<Character> list2=new ArrayList<>();
            int size=queue.size();
            while(size-->0) {
                TreeNode cur=queue.poll();
                list2.add(cur.val);
                if(cur.left!=null) {
                    queue.offer(cur.left);
                }
                if(cur.right!=null) {
                    queue.offer(cur.right);
                }
            }
            list.add(0,list2);                 //在0下标位置插入
        }
        return list;
    }
    //链接：https://www.nowcoder.com/questionTerminal/4b91205483694f449f94c179883c1fef
    //编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储)
    //例如如下的先序遍历字符串:ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树.建立起此二叉树以后再对二叉树进行中序遍历，输出遍历结果
    //创建一个二叉树
    //创建一个成员变量来获取字符串的每一个字符(不用考虑越界问题)
    public int i;
    public TreeNode creatTree(String s) {
        TreeNode root=null;
        if(s.charAt(i)!='#') {          //如果不为空
            root=new TreeNode(s.charAt(i));
            i++;
            root.left=creatTree(s);
            root.right=creatTree(s);
        }else {
            i++;
        }
        return root;
    }
    public boolean isCompleteTree(TreeNode root) {                       //判断是否为完全二叉树
        if(root==null) {
            return false;
        }
        //当这棵二叉树是完全二叉树或者满二叉数的时候，队列中是不可能出现null和结点同时存在的情况的
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur=queue.poll();
            if(cur==null) {                      //如果遇到了树中的空节点就停下来判断
                break;
            }else {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
        }
        while(!queue.isEmpty()) {
            TreeNode cur=queue.poll();
            if(cur!=null) {                   //到了这里表示已经开始判断，如果是完全二叉树或者满二叉树那么:
                return false;                 //队列中全部都是空节点，因为非空的都已经全部poll了，如果不是完全二叉树或者满二叉树那么:
            }                                 //就会出现有空也有非空的情况
        }
        return true;
    }
    //非递归实现前中后序遍历
    public List<Character> preorderNor(TreeNode root) {
        List<Character> list=new ArrayList<>();
        if(root==null) {
            return list;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()) {
            while(cur!=null) {     //先将左树全部放入栈并打印
                stack.push(cur);
                list.add(cur.val);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
        return list;
    }
    public List<Character> inorderNor(TreeNode root) {
        List<Character> list=new ArrayList<>();
        if(root==null) {
            return list;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            cur = top.right;
        }
        return list;
    }
    public List<Character> postorderNor(TreeNode root) {
        List<Character> list=new ArrayList<>();
        if(root==null) {
            return list;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while(cur!=null||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right==null||top.right==prev) {
                list.add(top.val);
                stack.pop();
                prev=top;     //定义一个变量记录下已经打印过得结点
            }else {
                cur = top.right;
            }
        }
        return list;
    }
}
